#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
template <typename T> inline void read(T &x) {
    x = 0; char ch = getchar(); int f = 1;
    while (!isdigit(ch) && ch ^ '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); x *= f;
}
int n,k,a[N],q,x,l,r,sum,lc[N],rc[N];
void print(long long x){
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
inline void get_first(){
	stack<int> stk;
	stk.push(0);a[0]=2e9;
	for(int i=1;i<=n;i++){
		while(a[stk.top()]<a[i]) stk.pop();
		lc[i]=lc[stk.top()]+1;
	}
	while(stk.size()>1) stk.pop();
	for(int i=n;i;i--){
		while(a[stk.top()]<a[i]) stk.pop();
		rc[i]=rc[stk.top()]+1;
	}
}
map<int,bool> hv;
bool D=1;
inline void get(int x){
	int c=a[x],l=x,r=x;
	while(1<l||r<n){
		while(l>1&&a[l-1]<=c) --l;
		while(r<n&&a[r+1]<=c) ++r;
		if(l>1&&(r==n||a[l-1]<=a[r+1])) sum+=k,c=a[--l];
		else if(r<n) sum+=k,c=a[++r];
	}sum+=n-1;
}
int main(){
	freopen("summer.in","r",stdin);
	freopen("summer.out","w",stdout);
	read(n),read(k);
	for(int i=1;i<=n;i++){
		read(a[i]);
		if(D&&hv[a[i]]) D=0;
		if(D) hv[a[i]]=1;
	}
	read(q);
	while(q--){
		read(x),read(l),read(r);
		swap(a[x],a[x+1]);
		if(D&&n>=500){
			get_first();
			for(int i=l;i<=r;i++) sum+=1ll*(lc[i]+rc[i]-1)*k+n-1;
		}else{
			sum=0;
			for(int i=l;i<=r;i++) get(i);
		}
		print(sum),putchar('\n');
	}
	return 0;
}

